﻿//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <assert.h>
//#include "结构体标头.h"
// C/C++ 学习网站：https://legacy.cplusplus.com 注意旧版本（搜索）和新版本

#include "common.h"

void change_num(int* num)
{ // 改数字，奇数位全变成 1 偶数位全变成 0
	int flag = *num > 0 ? 1 : -1; // 取符号
	*num = *num > 0 ? *num : -1 * *num; // 取绝对值
	int copy = 0;
	int value = 0;
	int bit = 0;
	while (*num > 0)
	{
		value = (*num % 10) % 2;
		*num /= 10;
		++bit;
		if (value)
		{
			int i;
			int temp = 1;
			for (i = 1; i < bit; ++i)
				temp *= 10; // 计算 10 的 bit - 1 次方
			copy += temp;
		}
	}
	if (flag == -1)
		*num = -1 * copy;
	else
		*num = copy;
}

void print_triangle(int n)
{ // 打印等腰直角三角形，n 行，每个 * 之间空格分割
	int i, j, k;
	for (i = 1; i <= n; ++i)
	{
		for (j = 1; j <= n - i; ++j)
			printf("  ");
		for (k = 1; k <= i; ++k)
			printf(" *");
		printf("\n");
	}
}

void rank_players()
{ // 确定比赛名次
/* 5 位运动员参加了 10 米台跳水比赛, 有人让他们预测比赛结果:
	A 选手说:B 第二, 我第三;
	B 选手说:我第二, E 第四;
	C 选手说:我第一, D 第二;
	D 选手说:C 最后, 我第三;
	E 选手说:我第四, A 第一;
比赛结束后, 每位选手都说对了一半, 请编程确定比赛的名次。*/
	int a, b, c, d, e;
	for (a = 1; a <= 5; ++a)
		for (b = 1; b <= 5; ++b)
			for (c = 1; c <= 5; ++c)
				for (d = 1; d <= 5; ++d)
					for (e = 1; e <= 5; ++e)
						if (1 == (b == 2) + (a == 3) &&
							1 == (b == 2) + (e == 4) &&
							1 == (c == 1) + (d == 2) &&
							1 == (c == 5) + (d == 3) &&
							1 == (e == 4) + (a == 1) &&
							a * b * c * d * e == 120 /*&&
							a + b + c + d + e == 15*/)
							printf("A->%d, B->%d, C->%d, D->%d, E->%d\n",
								a, b, c, d, e);
}

void search_killer()
{ // 找凶手
/*日本某地发生了一件谋杀案, 警察通过排查确定杀人凶手必为 4 个嫌疑犯的一个。
	以下为 4 个嫌疑犯的供词:
		A 说: 不是我。
		B 说: 是 C。
		C 说: 是 D。
		D 说: C 在胡说
已知 3 个人说了真话, 1 个人说的是假话。
现在请根据这些信息, 写一个程序来确定到底谁是凶手。*/
	char killer;
	for (killer = 'A'; killer <= 'D'; ++killer)
		if ((killer != 'A') + (killer == 'C') +
			(killer == 'D') + (killer != 'D') == 3)
			printf("%c is the killer.\n", killer);
}

void print_YangHui_triangle(int n)
{ // 打印杨辉三角，n 行，数字之间用空格分割
/* 杨辉三角示例：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
...... */
	int i, j;
	//int arr[n][n]; // 二维数组 C99 语法
	int** arr = (int**)malloc(n * sizeof(int*));	// 分配数组内存
	if (arr == NULL)
	{
		printf("Memory allocation failed.\n");
		exit(EXIT_FAILURE); // 内存分配失败，退出程序
	}
	for (i = 0; i < n; ++i)
	{
		arr[i] = (int*)malloc(n * sizeof(int)); // 分配内存
		if (arr == NULL)
		{
			printf("Memory allocation failed.\n");
			exit(EXIT_FAILURE);
		}
	}

	for (i = 0; i < n; ++i)
		if (!arr)
			for (j = 0; j < n; ++j)
				arr[i][j] = 0;	// 初始化数组

	int k;
	for (i = 1; i < n; ++i)
	{
		for (k = 0; k < (n - i); ++k)
			printf("  ");
		for (j = 1; j <= i; ++j)
		{
			if (j == 1 || j == i)
				arr[i][j] = 1;
			else
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
			if (0 == arr[i][j])
				printf("  ");
			else
				printf("%3d ", arr[i][j]); // 打印数字，宽度至少为 3
		}
		printf("\n");
	}

	// 释放内存
	for (i = 0; i < n; ++i)
		free(arr[i]);  // 先释放每一行的内存
	free(arr); // 最后释放指针数组本身
}

void reverse_string(char* left, char* right)
{ // 反转字符串，len 为字符串长度
	assert(left && right && left <= right); // 断言，保证左右指针指向不同的内存
	char temp;
	while (left < right)
	{
		temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
}

void left_rotate(char* arr, int k)
{ // 左旋转数组，k 为步长，比如 "abcdefg" 左旋转 2 步为 "cdefgab"
	int i, len = (int)strlen(arr); // 字符串长度，时间复杂度 O(n)
	k %= len; // 步长不能超过字符串长度
	// 创建一个临时数组保存前 k 个字符，空间换效率：时间复杂度 O(n + k)，推荐
	char* temp = (char*)malloc(k * sizeof(char));
	// 分配临时数组内存，空间复杂度 O(k * sizeof(char))
	if (temp == NULL)
	{
		printf("Memory allocation failed.\n");
		exit(EXIT_FAILURE);
	}
	// char temp[k]; // C99 语法，分配临时数组内存
	if (temp)
	{
		for (i = 0; i < k; ++i)
			temp[i] = *arr++; // 保存前 k 个字符到临时数组，时间复杂度 O(k)
		while (*arr)
			*(arr - k) = *arr++; // 左移后面的元素 k 个位置，时间复杂度 O(n - k)
		--arr; // 回到原数组末尾（'\0' 之前一个字节位置）
		for (i = k - 1; i >= 0; --i)
			*arr-- = temp[i]; // 回填回去 k 个字符，时间复杂度 O(k)
	}
	free(temp); // 释放临时数组内存

	// 每次只是左旋 1 个字符，重复 k 次的实现，时间复杂度 O(n * k)，效率低，不推荐
	/*int j;
	for (i = 0; i < k; ++i)
	{ // 左旋 k 次，时间复杂度 O(k)
		char temp = *arr; // 保存第一个字符
		for (j = 1; j < len; ++j)
		{ // 左移 k 个字符，时间复杂度 O(n)
			arr[j - 1] = arr[j]; // 左移后面的元素
			if (j == len - 1)
				arr[len - 1] = temp; // 回填第一个字符
		}
	} */

	// 三次翻转实现，时间复杂度 O(n + n)，其次推荐，空间使用比上一个方法大些
	/* reverse_string(arr, arr + k - 1);
		// 翻转前 k 个字符，时间复杂度 O(k)
	reverse_string(arr + k, arr + len - 1);
		// 翻转后 n - k 个字符，时间复杂度 O(n - k)
	reverse_string(arr, arr + len - 1); // 翻转整个字符串，时间复杂度 O(n) */
}

int binary_search(int* sorted_arr, int left, int right, int value)
{ // 二分查找法：在有序数组 arr 中查找 value，返回其下标，不存在返回 -1
	if (value < sorted_arr[left] || value > sorted_arr[right])
		return -1; // 值不在数组范围内
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (sorted_arr[mid] == value)
			return mid;
		else if (sorted_arr[mid] < value)
			left = mid + 1;
		else
			right = mid - 1;
	}
	return -1; // 未找到
}

struct coord search_num_arr(int arr[][5], int rows, int cols, int value)
{ // 在杨氏矩阵二维数组中搜索数字，返回坐标，不存在返回 -1 这里 arr[][5] 同 (*arr)[5]
/* 杨氏矩阵示例：
	1 3 6
	2 7 10
	8 9 15
即从左上角开始，每一行值递增，每一列值也递增 */
	struct coord cod = { -1, -1 }; // 初始化坐标结构体
	if (value < arr[0][0] || value > arr[rows - 1][cols - 1])
	{
		printf("not found value.\n");
		return cod; // 值不在数组范围内
	}
	int x = 0, y = cols - 1; // 右上角坐标

	// 二分查找每一行，适用于杨氏矩阵以及每一行递增、每一列不递增的情况
	/* for (x = 0; x < rows; ++x)
		if (-1 == (y = binary_search(arr + x, 0, cols - 1, value)))
			continue; // 未找到，继续搜索下一行
		else
		{
			printf("found value at (%d, %d)\n", x, y); // 找到，输出坐标
			cod.x = x;
			cod.y = y;
			return cod; // 找到，返回坐标结构体
		} */

		// 以右上角为起点，向左下角、右下角搜索，只适用于杨氏矩阵的情况，效率高
	while (x <= cols - 1 && y >= 0)
		if (value == arr[x][y])
		{
			printf("found value at (%d, %d)\n", x, y); // 找到，输出坐标
			cod.x = x;
			cod.y = y;
			return cod; // 找到，返回坐标
		}
		else if (value < arr[x][y])
			--y; // 左移
		else
			++x; // 下移

	printf("not found value.\n");
	return cod; // 找完了，未找到，返回初始化坐标结构体
}

char* right_rotate(char* arr, int k)
{ // 右旋转数组，k 为步长，比如 "abcdefg" 右旋转 2 步为 "fgabcde"
	int i, len = (int)strlen(arr); // 字符串长度，时间复杂度 O(n)
	k %= len; // 步长不能超过字符串长度
	if (k == 0)
		return arr; // 步长为 0，返回原数组

	// 创建一个临时数组保存前 k 个字符，空间换效率：时间复杂度 O(n + k)，推荐
	char* temp = (char*)malloc(k * sizeof(char));
	// 分配临时数组内存，空间复杂度 O(k * sizeof(char))
	if (temp == NULL)
	{
		printf("Memory allocation failed.\n");
		exit(EXIT_FAILURE);
	}
	// char temp[k]; // C99 语法，分配临时数组内存
	//char* arr_start = arr; // 保存原数组首元素地址
	if (temp)
	{
		arr += len - 1; // 移动到数组末尾（'\0' 之前一个字节位置）
		for (i = k - 1; i >= 0; --i)
			temp[i] = *arr--; // 保存后 k 个字符到临时数组，时间复杂度 O(k)
		for (i = len - k - 1; i >= 0; --i)
			*(arr + k) = *arr--; // 右移前面的 n - k 个元素，时间复杂度 O(n - k)
		arr++; // 回到原数组首元素位置
		for (i = k - 1; i >= 0; --i)
			arr[i] = temp[i]; // 回填回去 k 个字符，时间复杂度 O(k)
	}
	free(temp); // 释放临时数组内存
	return arr; // 返回原数组首元素地址
}

int is_rotate_right(char* s1, int len1, char* s2, int len2)
{ // 判断 s1 是否为 s2 旋转后的字符串，返回正整数则为旋转字符串，-1 则不是
	if (len1 != len2 || 0 == len1 || 0 == len2)
		return -1; // 字符串长度不同或为空，不是旋转字符串
	else if (0 == strcmp(s1, s2))
		return 0; // 字符串相同，是旋转 0 次字符串

	int i, j;
	char c;
	for (i = 1; i < len1; ++i)
	{
		/*if (0 == strcmp(s1, right_rotate(s2, 1))) // 每次右旋 1 次进行比较
			return i; // 找到旋转字符串，返回右旋转位数
		else
			continue; // 未找到旋转字符串，继续搜索 */

		c = *(s2 + len1 - 1); // 每次保存最后一个字符
		for (j = len1 - 1; j >= 1; --j)
			*(s2 + j) = *(s2 + j - 1); // 右移前面的元素
		*s2 = c; // 回填第一个字符
		if (0 == strcmp(s1, s2))
			return i; // 找到旋转字符串，返回右旋转位数
		else
			continue; // 未找到旋转字符串，继续搜索
	}
	return -1; // 未找到旋转字符串，返回 0
}

int is_rotate_left(char* s1, int len1, char* s2, int len2)
{ // 判断 s1 是否为 s2 的旋转字符串，返回正整数则为左旋转字符串，-1 则不是，库函数版本
	if (len1 != len2 || 0 == len1 || 0 == len2)
		return -1; // 字符串长度不同或为空，不是旋转字符串
	else if (0 == strcmp(s1, s2))
		return 0; // 字符串相同，是旋转 0 次字符串

	char* s3 = (char*)malloc(len2 * sizeof(char) * 2 + 1); // 分配临时数组内存
	if (s3)
	{
		strncpy(s3, s2, len1); // 复制 s2 到 s3
		s3[len1] = '\0'; // 追加结束符
		strncat(s3, s2, len1); // 追加 s2 到 s3
		s3[len1 * 2] = '\0'; // 追加结束符
		char* p_left = strstr(s3, s1); // 找到 s1 在 s3 中的位置
		if (p_left)
			return (int)(p_left - s3); // 找到旋转字符串，返回左旋转位数
		else
			return -1; // 未找到旋转字符串，返回 -1
	}
	printf("Memory allocation failed.\n");
	return -1; // 内存分配失败，也返回 -1
}

int** transpose_matrix(int** arr, int rows, int cols)
{ // 转置矩阵，arr 为原矩阵，rows 为行数，cols 为列数，返回转置后的矩阵
	int** tran_arr = (int**)malloc(cols * sizeof(int*));
	//列 -> 行，分配新行内存
	if (tran_arr)
	{
		int i, j;
		for (i = 0; i < cols; ++i) // 这里的 cols 表示 tran_arr 的行数
		{	// 行 -> 列，分配新列内存
			tran_arr[i] = (int*)malloc(rows * sizeof(int));
			if (!tran_arr[i])
			{
				printf("Memory allocation failed.\n");
				for (j = 0; j < i; ++j)
					free(tran_arr[j]); // 释放已分配的行内存
				free(tran_arr); // 释放已分配的行指针数组
				return NULL; // 内存分配失败，返回 NULL
			}
		}
		for (i = 0; i < rows; ++i)
			for (j = 0; j < cols; ++j)
				tran_arr[j][i] = arr[i][j]; // 转置矩阵
		return tran_arr; // 成功转置，返回转置后的矩阵
	}
	else
	{
		printf("Memory allocation failed.\n");
		return NULL; // 失败则返回 NULL
	}
}

int is_upper_triangle(int** arr, int rows, int cols)
{ // 判断矩阵是否为上三角矩阵，返回 1 则是，0 则不是
/* 上三角矩阵示例：
	1 2 3
	0 4 5
	0 0 6
即主对角线（左上角到右下角的连线）以下的元素均为 0 的矩阵 */
	if (rows != cols || 0 == rows || 0 == cols)
		return 0; // 不是上三角矩阵
	int i, j;
	for (i = 1; i < rows; ++i)
		for (j = 0; j < i; ++j)
			if (arr[i][j] != 0)
				return 0; // 不是上三角矩阵
	/*else
		continue; // 继续搜索*/
	return 1; // 是上三角矩阵
}

char* is_sorted(int* arr, int len)
{ // 判断数组从 arr 到 arr + len 位置是否有序，返回字符串
	char* result = (char*)malloc(19 * sizeof(char)); // 结果字符串
	if (len < 2)
	{
		strcpy(result, "数组过短，不判断。"); // 长度小于 2，肯定有序
		return result;
	}
	int flag1 = 0, flag2 = 0, i; // 标记是否有序，flag1 为升序标记，flag2 为降序标记
	for (i = 1; i < len; ++i)
	{
		if (arr[i] > arr[i - 1])
			flag1 = 1; // 升序标记
		else if (arr[i] < arr[i - 1])
			flag2 = 1; // 降序标记
		else
			continue; // 相等，继续搜索
	}
	if (0 == flag1 + flag2) // 同时有升序和降序，不是有序数组
		strcpy(result, "数组所有元素相等。");
	else if (2 == flag1 + flag2) // 既有升序又有降序，不是有序数组
		strcpy(result, "数组无序。");
	else if (flag1 && !flag2) // 只有升序，是有序数组
		strcpy(result, "升序数组。");
	else
		strcpy(result, "降序数组。");
	return result; // 返回结果字符串
}
